20220226-TIL

오늘 알고리즘 문제는 수색 범위 내의 도시들을 탐색했을 때의 기대 이득을 구해야 하는 문제였다.

• 서강 그라운드 문제는 최단 경로를 구한 후에 수색 가능한 도시들만 확인하는 식으로 풀었다.
• 플로이드 알고리즘으로 최단 경로/거리를 구한 후, 방문 가능한 도시를 확인하도록 구현했다.
• 처음에는 경로 복원 중에 방문한 도시들을 집합에 기록해둔 후, 이득을 계산하도록 구현했다.
• 이후, 수색 범위 내에 있는 도시만 방문하게 된다는 것을 깨달았고, 경로 복원 부분을 없앴다.

카카오 신입공채 2차 코딩 테스트 문제 해설 내용을 정리했다. (나중에 직접 풀어보긴 해야 할 듯;)